package main

import (
	"fmt"
	"log"
	"math"
	"math/rand"
	"reflect"
	"regexp"
	"sort"
	"sync"
	"sync/atomic"
	"unsafe"
)

func main() {

}

// maxSubArr 求slice连续元素的最大和
func maxSubArr(nums []int) int {
	var getMax func(a, b int) int
	getMax = func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	sum := math.MinInt32
	currentSum := 0
	for _, num := range nums {
		// 如果currentSum+num更大，则继续累加，否则重置currentSum成当前元素，保证元素连续累加
		currentSum = getMax(num, currentSum+num)
		sum = getMax(sum, currentSum)
	}
	return sum
}

func isNarcissistic(num int) bool {
	sum := 0
	temp := num
	for temp > 0 {
		digit := temp % 10
		sum += digit * digit * digit
		temp /= 10
	}
	return sum == num
}

func splitToNarcissisticSubStrings(s string) [][]string {
	var result [][]string
	n := len(s)

	for i := 0; i < (1 << (n - 1)); i++ {
		var subStrings []string
		start := 0
		sum := 0
		valid := true
		for j := 0; j < n; j++ {
			sum += int(s[j])
			if (i & (1 << j)) != 0 {
				if isNarcissistic(sum) {
					subStrings = append(subStrings, s[start:j+1])
					start = j + 1
					sum = 0
				} else {
					valid = false
					break
				}
			}
		}
		if valid && isNarcissistic(sum) {
			subStrings = append(subStrings, s[start:])
			result = append(result, subStrings)
		}
	}
	return result
}

func one() {
	a := ""
	for {
		n, _ := fmt.Scan(&a)
		if n == 0 {
			break
		} else {
			res := splitToNarcissisticSubStrings(a)
			if len(res) == 0 {
				fmt.Println(0)
				return
			}

			if len(res) > 1 {
				fmt.Println(-1)
				return
			}
			sum := 0
			for range res[0] {
				sum++
			}
			fmt.Println(sum)
		}
	}

}

func minStartTime(n int, s [][]int, target int) int {
	memo := make([]int, n)
	visited := make([]bool, n)
	var getMax func(a, b int) int
	getMax = func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}
	var dfs func(int) int
	dfs = func(i int) int {
		if visited[i] {
			return memo[i]
		}
		visited[i] = true
		time := s[i][i]
		for j := 0; j < n; j++ {
			if s[i][j] == 1 {
				time = getMax(time, dfs(j)+s[i][i])
			}
		}
		memo[i] = time
		return time
	}
	return dfs(target - 1)
}

func tow() {
	s := [][]int{{}}
	for {
		n, _ := fmt.Scan(&s)
		if n == 0 {
			break
		} else {
			n := s[0][0]
			target := s[len(s)-1][0]
			s = s[1 : len(s)-1]
			res := minStartTime(n, s, target)
			fmt.Println(res)
		}
	}
}

var (
	l    = 5
	rep  = regexp.MustCompile(`(a.qq.com)`)
	from = "***"
	m    = map[string]struct{}{
		"a.qq.com": {},
		"b.qq.com": {},
	}
)

func strReplace(s string, from string) string {
	return rep.ReplaceAllString(s, from)
}

// idx恰巧落在b.qq.com的0号索引上
func isSpecialStr(s []rune, idx int) (string, bool) {
	for special, _ := range m {
		specialLen := idx + len([]rune(special))
		if specialLen <= len(s) && string(s[idx:specialLen]) == special {
			return special, true
		}
	}
	return "", false
}

// todo 这里如果idx落在b.qq.com中间位置或者落在之前不足5的位置呢？比如落在‘件’上
func isSpecialStr2(s []rune, idx int) (int, bool) {

	return -1, false
}

func doStr() {
	s := "a.qq.com thank you,这里还有中文的邮件：b.qq.com，谢谢"
	var strs []string
	newS := []rune(s)
	newSLen := len(newS)
	i := 0
	for i < newSLen {
		end := i + l
		if specialStr, ok := isSpecialStr(newS, i); ok {
			end = i + len([]rune(specialStr))
		}
		if end > newSLen {
			end = newSLen
		}
		strs = append(strs, string(newS[i:end]))
		i = end
	}
	log.Print(strs)
}

// threeSum 三数之和：给定一个数组，找到所有三数之和是0的组合。三数满足i!=j i!=k j!=k
func threeSum(nums []int) [][]int {
	// 结果数组
	var result [][]int

	// 先排序数组
	sort.Ints(nums)

	// 遍历数组
	for i := 0; i < len(nums); i++ {
		// 跳过重复元素
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}

		// 使用双指针查找三元组
		left, right := i+1, len(nums)-1
		for left < right {
			sum := nums[i] + nums[left] + nums[right]
			if sum == 0 {
				// 找到一个三元组，添加到结果中
				result = append(result, []int{nums[i], nums[left], nums[right]})

				// 跳过重复的元素
				for left < right && nums[left] == nums[left+1] {
					left++
				}
				for left < right && nums[right] == nums[right-1] {
					right--
				}

				// 移动指针
				left++
				right--
			} else if sum < 0 {
				left++ // 增大 sum
			} else {
				right-- // 减小 sum
			}
		}
	}

	return result
}

type job struct {
	start int
	end   int
}

func product(val chan<- int, wg *sync.WaitGroup, j job) {
	defer wg.Done()
	for i := j.start; i <= j.end; i++ {
		val <- i
	}
}

func consumer(val <-chan int, wg *sync.WaitGroup) {
	defer wg.Done()
	for {
		select {
		case n := <-val:
			log.Print(n)
		default:
			return
		}
	}
}

// doJob 模拟一个生产者消费者模型
func doJob() {
	j := job{
		start: 1,
		end:   10,
	}
	wg := &sync.WaitGroup{}
	wg.Add(10)
	ch := make(chan int, 10)
	for i := 0; i < 10; i++ {
		go product(ch, wg, j)
	}
	wg.Add(10)
	for i := 0; i < 10; i++ {
		go consumer(ch, wg)
	}
	wg.Wait()
}

type treeT interface {
	~int | ~string
}

type tree[T treeT] struct {
	val   T
	left  *tree[T]
	right *tree[T]
}

// levelTraversal 按层级遍历二叉树之队列写法
func levelTraversal[T treeT](root *tree[T]) [][]T {
	if root == nil {
		return nil
	}
	var res [][]T
	queue := []*tree[T]{root}
	for len(queue) > 0 {
		var level []T
		size := len(queue)
		for i := 0; i < size; i++ {
			node := queue[0]
			queue = queue[1:]
			level = append(level, node.val)
			if node.left != nil {
				queue = append(queue, node.left)
			}
			if node.right != nil {
				queue = append(queue, node.right)
			}
		}
		res = append(res, level)
	}
	return res
}

func product2(ch chan<- int) {
	for i := 0; i < 10; i++ {
		ch <- i
	}
}

func consumer2() chan<- int {
	ch := make(chan int)
	go func() {
		for {
			log.Print(<-ch)
		}
	}()
	return ch
}

// doJob2 模拟一个生产者消费者模型
func doJob2() {
	wg := sync.WaitGroup{}
	s := make([]chan<- int, 10)
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func(i int) {
			defer wg.Done()
			s[i] = consumer2()
			product2(s[i])
		}(i)
	}
	wg.Wait()
}

// 定义缓冲区大小
const bufferSize = 5

// 模拟生产者生成数据
func producer3(ch chan<- int, wg *sync.WaitGroup) {
	defer wg.Done()
	for i := 0; i < 2; i++ {
		// 模拟生产数据
		fmt.Printf("生产者生产了数据: %d\n", i)
		ch <- i // 将数据放入缓冲区
	}
}

// 模拟消费者处理数据
func consumer3(wg *sync.WaitGroup) chan<- int {
	ch := make(chan int)
	go func() {
		for item := range ch {
			// 模拟消费者消费数据
			fmt.Printf("消费者消费了数据: %d\n", item)
		}
		wg.Done()
	}()
	return ch
}

// doJob3 生产者消费者模型第三种
func doJob3() {
	wg := &sync.WaitGroup{}
	wg.Add(1)
	//for i := 0; i < 10; i++ {
	ch := consumer3(wg)
	go producer3(ch, wg)
	//}
	wg.Wait()
}

var (
	n           = 10
	start int32 = 0
	end   int32 = 100
)

type worker struct {
	done func()
}

func product4(ch chan int, w worker) {
	defer w.done()
	for start < end {
		if start == 99 {
			return
		}
		atomic.AddInt32(&start, 1)
		ch <- int(start)
	}
}

func consumer4(ch chan int, id int) {
	for n := range ch {
		log.Printf("from %d->%d", id, n)
	}
}

// doJob4生产者消费者模型第四种
func doJob4() {
	ch := make(chan int)
	done := make(chan struct{})

	w := worker{
		done: func() {
			done <- struct{}{}
		},
	}
	for i := 0; i < n; i++ {
		go product4(ch, w)
	}
	for i := 0; i < n; i++ {
		go consumer4(ch, i)
		<-done
	}
}

// isValid 判断是否是有效括号
func isValid(s string) bool {
	m := map[rune]rune{
		'(': ')',
		'[': ']',
		'{': '}',
	}
	var stack []rune
	for _, v := range s {
		matched, ok := m[v]
		if ok {
			stack = append(stack, matched)
		} else {
			if len(stack) == 0 || v != stack[len(stack)-1] {
				return false
			}
			stack = stack[:len(stack)-1]
		}
	}
	return len(stack) == 0
}

// getTreeSum 二叉树根节点到叶子节点的路径和
type treeInt struct {
	val   int
	left  *treeInt
	right *treeInt
}

func getTreeSum(root *treeInt, sum int) int {
	if root == nil {
		return 0
	}
	sum = sum*10 + root.val
	if root.left == nil && root.right == nil {
		return sum
	}
	return getTreeSum(root.left, sum) + getTreeSum(root.right, sum)
}

func groupAnagrams(strs []string) [][]string {
	// Create a map to hold the groups
	anagramGroups := make(map[string][]string)

	// Iterate through each string in strs
	for _, str := range strs {
		// Generate a key based on character frequencies
		key := getFrequencyKey(str)

		// Group the strings by their frequency key
		anagramGroups[key] = append(anagramGroups[key], str)
	}

	// Convert the map values to a 2D slice
	var result [][]string
	for _, group := range anagramGroups {
		result = append(result, group)
	}

	return result
}

// Helper function to generate a frequency key for a string
func getFrequencyKey(str string) string {
	// Create a frequency array for 26 lowercase English letters
	freq := make([]int, 26)
	for _, char := range str {
		freq[char-'a']++
	}

	// Convert the frequency array into a string to use as a key
	key := ""
	for _, count := range freq {
		key += fmt.Sprintf("#%d", count)
	}
	return key
}

type listT interface {
	~int | ~string
}

type list[T listT] struct {
	value T
	next  *list[T]
}

// mergeSortedList 合并两个有序链表
func mergeSortedList[T listT](l1, l2 *list[T]) *list[T] {
	dummy := &list[T]{}
	current := dummy
	for l1 != nil && l2 != nil {
		if l1.value < l2.value {
			current.next = l1
			l1 = l1.next
		} else {
			current.next = l2
			l2 = l2.next
		}
		current = current.next
	}
	if l1 != nil {
		current.next = l1
	} else {
		current.next = l2
	}
	return dummy
}

// maxReset 最大回撤数
func maxReset(numbers []float64) float64 {
	if len(numbers) == 0 {
		return 0
	}
	maxPrice := numbers[0]
	maxRst := 0.0
	for _, number := range numbers[1:] {
		if number > maxPrice {
			maxPrice = number
		} else {
			down := maxPrice - number
			if maxRst < down {
				maxRst = down
			}
		}
	}
	return maxRst
}

func rand7() int {
	return rand.Intn(7) + 1
}

// 用rand7均匀的生成rand10
func rand10() int {
	for {
		r1, r2 := rand7(), rand7()
		idx := (r1-1)*7 + r2
		if idx <= 40 {
			//保证均匀性，直接idx%10不能保证均匀性且10的结果不对
			return (idx-1)%10 + 1
		}
	}
}

// stringToBytes 字符串转成字节数组
func stringToBytes() {
	s := "hello word"
	// 获取字符串的底层指针
	sHeahder := (*reflect.StringHeader)(unsafe.Pointer(&s))
	sliceHeader := &reflect.SliceHeader{
		Data: sHeahder.Data,
		Len:  sHeahder.Len,
		Cap:  sHeahder.Len,
	}
	// 将字符串转成bytes数组
	bytes := *(*[]byte)(unsafe.Pointer(sliceHeader))
	log.Print(string(bytes))
}
